#include <iostream>
#include "linearList.h"
using namespace std;

//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}

//初始化顺序表
sequenceList::sequenceList(const int& capacity,const int& number,float arrar[] )
{
    curNumberOfItem=number;         //初始化数组长度
    maxCapcity=capacity;            //顺序表容量
    myList=new float[maxCapcity];   //初始化数组

    //将数组元素复制到顺序表中
    for(int i=0;i<curNumberOfItem;i++)
    {
        myList[i]=arrar[i];
    }
}

//销毁顺序表
sequenceList::~sequenceList()
{
    //释放数组
    delete[] myList;
}

//添加元素
bool sequenceList::addItem(const float& Item)
{
    //添加新元素前若当前顺序表容量大于或等于最大容量，代表顺序表已满，插入失败
    if(curNumberOfItem>=maxCapcity)
    {
        return false;
    }
    //否则，将新元素添加至curNumberOfItem+1的位置并更新当前元素数量
    myList[curNumberOfItem++]=Item;
    return true;
}

//插入元素
bool sequenceList::insertItem(const int& index,const float& Item)
{
    //在线性表中第index个位置插入新元素Item
    //index的合法值为0<=index<=curNumberOfItem
    if(index<0||index>curNumberOfItem||curNumberOfItem>=maxCapcity)
    {
        return false;   //插入位置无效或顺序表容量已满
    }
    //将index位置及其之后元素均右移一位
    for(int i=curNumberOfItem;i>index;--i)
    {
        myList[i]=myList[i-1];
    }
    myList[index]=Item;
    curNumberOfItem++;      //更新当前元素数量
    return true;
}

//删除元素
int sequenceList::deleteItem(const float& Item)
{
    //返回删除元素的位置index，否则返回-1
    //在线性表中从左向右查找
    for(int i=0;i<curNumberOfItem;i++)
    {
        if(myList[i]==Item)
        {
            //若找到目标元素，将线性表i位置右侧元素依次左移一位实现覆盖
            for(;i<curNumberOfItem-1;i++)
            {
                myList[i]=myList[i+1];
            }
            curNumberOfItem--;      //更新元素数量
            return i;   //将删除位置返回
        }
    }
    return -1;
}

//查找元素（按序号找）
bool sequenceList::locate(const int& index,float& val)
{
    //index合法值为0<=index<curNumberOfItem
    if(index<0||index>=curNumberOfItem)
    {
        return false;
    }
    val=myList[index];      //将目标位置找到的值放入val中
    return true;
}

//查找元素（按值找）
int sequenceList::locate(const float& Item)
{
    //将顺序表从起始位置开始查找
    for(int i=0;i<curNumberOfItem;i++)
    {
        if(myList[i]==Item)
        {
            return i;       //返回目标元素下标
        }
    }
    return -1;
}

//倒序排列元素（使用原空间）
void sequenceList::reverse()
{
    int start=0;
    int end=curNumberOfItem-1;
    while(start<end)
    {
        float temp=myList[start];
        myList[start]=myList[end];
        myList[end]=temp;
        start++;
        end--;
    }
}


//listNode构造函数
listNode::listNode(float nodeData,listNode* succ):data(nodeData),next(succ){}

//listNode析构函数
listNode::~listNode(){}

//linkList默认构造函数
linkList::linkList():firstNode(new listNode()),curNode(nullptr),lastNode(nullptr),listSize(0){}

//初始化链表
linkList::linkList(const int& length,float arr[]):listSize(0),firstNode(new listNode(0)), lastNode(nullptr)
{
    for(int i=0;i<length;i++)
    {
        tailInsertItem(arr[i]);     //使用尾插法插入元素
    }
}

//销毁链表
linkList::~linkList()
{
    //检查firstNode是否为nullptr,若不为nullptr,链表非空，继续删除
    //实现删除时，使头节点依次右移，将原头节点释放
    while(firstNode)
    {
        listNode* temp=firstNode;
        firstNode=firstNode->next;
        delete temp;
    }
}

//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}


//插入元素（头插法）
bool linkList::headInsertItem(const float& Item)
{
    listNode* newNode=new listNode(Item,firstNode->next);
    firstNode->next=newNode;
    if(listSize==0)
    {
        lastNode=newNode;     //若此时插入的Item值为链表中第一个元素，则更新尾指针指向该元素
    }
    listSize++;
    return true;
}

//插入元素（尾插法）
bool linkList::tailInsertItem(const float& Item)
{
    //创建新的listNode
    listNode* newNode=new listNode(Item);
    if(listSize==0)
    {
        //若此前链表为空，则头指针尾指针均指向新元素
        firstNode->next=newNode;
        lastNode=newNode;
    }
    else
    {
        //若链表非空，则将倒数第二个元素链接到新元素，更新尾指针即可
        lastNode->next=newNode;
        lastNode=newNode;
    }
    listSize++;
    return true;
}

//插入元素
int linkList::insertItem(const int& index,const float& value)
{
    //插入元素到index位置，若成功则返回插入位置
    //index的合法位置为0<=index<listSize
    if(index<0||index>listSize)
    {
        return -1;
    }
    listNode* newNode=new listNode(value);
    //若插入位置为开头
    if(index==0)
    {
        newNode->next=firstNode->next;
        firstNode->next=newNode;
        if(listSize==0)
        {
            lastNode=newNode;
        }
    }
    //若插入位置为结尾
    else if(index==listSize)
    {
        lastNode->next=newNode;
        lastNode=newNode;
    }
    //若在中间位置插入,则需要找到插入位置之前的一个元素
    else if(index>0&&index<listSize)
    {
        listNode* current=firstNode->next;
        for(int i=0;i<index-1;i++)
        {
            current=current->next;      //跳出for循环前最后一次，current执行操作后为index-1位置处元素
        }
        newNode->next=current->next;
        current->next=newNode;
    }
    listSize++;
    return index;
}

//删除元素
int linkList::deleteItem(const float& value) 
{
    listNode* current = firstNode;      //当前指针
    listNode* prev = NULL;              //前一个指针，初始为NULL
    //遍历链表，搜索目标值
    for(int i = 0; i < listSize; i++)
    {
        prev = current;
        current = current -> next;      //将current移动到第一个元素
        //查找元素
        if(current -> data == value)
        { 
            prev -> next = current -> next; 
            //若目标值在尾结点
            if(current == lastNode) 
            {
				lastNode = prev; 
			}
            delete(current); 
            listSize--;
            return i;
        }
    }
    return -1;
}

//查找元素（按序号查找）
bool linkList::locate(const int& index,float& val)
{
    //按序号查找元素，若成功将值放入val中并返回true
    //index的合法值为0<=index<listSize
    if(index<0||index>=listSize)
    {
        return false;
    }
    listNode* current=firstNode;
    for(int i=0;i<index;i++)
    {
        current=current->next;      //使current移动到目标位置元素
    }
    val=current->data;
    return true;
}

//查找元素（按值找）
int linkList::locate(const float& value)
{
    //若找到则返回其位置，未找到返回-1
    //从头节点开始遍历列表
    listNode* current=firstNode->next;
    int index=0;    //记录当前位置
    while(current)
    {
        if(current->data==value)
        {
            return index;
        }
        current=current->next;
        index++;
    }
    return -1;
}

//递增排序
void linkList::ascendingOrder()
{
    //类比冒泡排序实现递增排序
    for(int i=0;i<listSize-1;i++)
    {
        listNode* current=firstNode->next;    //重置listNode，使每次外层循环依旧从头节点开始
        for(int j=0;j<listSize-i-1;j++)
        {
            if(current->data>current->next->data)
            {
                float temp=current->data;
                current->data=current->next->data;
                current->next->data=temp;
            }
            current=current->next;
        }
    }
}

//倒序排列元素
void linkList::reverse()
{
    //使指针指向反转
    //定义变量存储当前元素的前一个和后一个元素
    listNode* prev=nullptr;     //前一个元素
    listNode* current=firstNode->next;    //将当前元素初始化为头节点
    listNode* next=nullptr;     //后一个元素
    
    while(current)
    {
        next=current->next;     //使next指向后一个元素，避免反转指针后下一个节点丢失
        current->next=prev;     //逆转指针指向
        prev=current;
        current=next;   //移动到下一个节点
    }
    lastNode=firstNode->next;     //更新尾结点为原先头节点
    firstNode->next=prev;         //跳出循环前最后一次循环语句执行后prev指向最后一个元素
}

//合并两个链表
void merge(linkList& alist,linkList& blist)
{
    listNode* currentB=blist.getFirstNode();

    while(currentB)
    {
        alist.tailInsertItem(currentB->data);
        currentB=currentB->next;
    }

    //对于递减的实现，先利用递增函数实现增序排列，再利用反转函数将指针指向反转实现递减 
    alist.ascendingOrder();
    alist.reverse();
    
}